package com.itheima.leetcode.od.c.dynamicprogramming;

import java.util.*;
import java.util.stream.Collectors;

/**
 * <h3>国际移动用户识别码(IMSI)匹配</h3>
 * <h4>最长子字符串</h4>
 */
public class IMSI {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入
        String configs = scanner.nextLine().trim();
        String imsi = scanner.nextLine().trim();

        // 输出结果
        System.out.println(solveImsiMatching(configs, imsi));

        scanner.close();
    }

    private static String solveImsiMatching(String configs, String imsi) {
        // 分割配置字符串
        String[] patterns = configs.split(",");

        // 存储匹配成功的配置
        List<String> matched = new ArrayList<>();

        // 检查每个配置是否匹配
        for (String pattern : patterns) {
            if (matchPattern(pattern, imsi)) {
                matched.add(pattern);
            }
        }

        // 如果没有匹配的配置，返回"null"
        if (matched.isEmpty()) {
            return "null";
        }

        return matched.stream()
                .sorted((a, b) -> a.compareTo(b))
                .collect(Collectors.joining(","));
    }

    private static boolean matchPattern(String pattern, String imsi) {
        // 如果模式中没有特殊字符，直接比较
        if (!pattern.contains("*") && !pattern.contains("?")) {
            return pattern.equals(imsi);
        }

        // dp[i][j] 表示pattern的前i个字符能否匹配imsi的前j个字符
        boolean[][] dp = new boolean[pattern.length() + 1][imsi.length() + 1];

        // 空串匹配空串
        dp[0][0] = true;

        // 处理只有*的情况可以匹配空串
        for (int i = 1; i <= pattern.length(); i++) {
            if (pattern.charAt(i - 1) == '*') {
                dp[i][0] = dp[i - 1][0];
            }
        }

        // 填充dp数组
        for (int i = 1; i <= pattern.length(); i++) {
            char currChar = pattern.charAt(i - 1);
            for (int j = 1; j <= imsi.length(); j++) {
                if (currChar == '*') {
                    // *可以匹配0个或多个字符
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1]; // 重点多思考 以*为参考 dp[i - 1][j] 其实是第一次匹配 dp[i][j - 1] *匹配后后面都为true
                } else if (currChar == '?') {
                    // ?只能匹配奇数位置的单个字符
                    if ((j - 1) % 2 == 1) {  // j-1是实际的索引
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                } else {
                    // 普通字符必须完全匹配
                    dp[i][j] = dp[i - 1][j - 1] && currChar == imsi.charAt(j - 1);
                }
            }
        }

        return dp[pattern.length()][imsi.length()];
    }
}